def make_mat(m, n):
    mat = []
    for i in range(m):
        mat.append([None] * n)
    return mat

INF = 1e8


def build_best_solution(s, i, j):
    if i == j:
        print("A[%d]" % i, end="")
    else:
        print("(", end="")
        build_best_solution(s, i, s[i][j])
        build_best_solution(s, s[i][j]+1, j)
        print(")", end="")


def matrix_chain(p):
    n = len(p) - 1  # p index start form 1
    m = make_mat(n+1, n+1)
    s = make_mat(n+1, n+1)

    # dynamic search
    for i in range(1, n+1):
        m[i][i] = 0

    for l in range(2, n+1):
        for i in range(1, n-l+2):
            j = i + l - 1
            m[i][j] = INF
            for k in range(i, j):
                q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k

    build_best_solution(s, 1, n)

if __name__ == '__main__':
    cases = [
        [9, 4, 10, 7, 20],
        [3, 5, 2, 1, 10],
        [2, 7, 3, 6, 10],
        [10, 3, 15, 12, 7, 2],
        [7, 2, 4, 15, 20, 5]
    ]
    for c in cases:
        matrix_chain(c)
        print("")
